The present invention relates to methods of transmitting “streaming data”, such as video or audio content, to multiple clients at arbitrary delivery times within a delivery period and as selected by the clients. In particular, the present invention provides a method of reducing the bandwidth or other costs associated with transmitting such data at different delivery times to different clients.
“Streaming data” is data that a client will process sequentially as it is received during a transmission, under a timeliness constraint requiring progress in the reception of the data. Examples of streaming data are video and audio programs, including movies, television shows, news clips, product advertisements, medical or recreational information, or education programs. This list of examples is not exhaustive. “On-demand delivery” of streaming data is the delivery of streaming data triggered by client requests for that data, rather than simply by reaching a previously defined point in time. For example, in a video on-demand (VOD) system a customer might be able to request a video program at any time, with the expectation that the video would be viewable within a small time following the request.
Programs of streaming data may be stored at and transmitted from a server to clients via phone lines, cable, broadcast radio, satellite links or other media. The server may be a single machine or a set of machines that together provide a service.
On-demand delivery may be provided by making a separate transmission of data to each client when the client request arrives. This approach is simple and works with standard receiving devices but has the disadvantage of requiring a large number of transmission channels, one for each new client. The transmission capacity of the server and the intervening communications medium (phone lines, cable etc.) is termed “bandwidth,” referring generally to the amount of data transmitted in a given time interval. For this simple scheme of providing on-demand delivery of streaming data, the bandwidth required to serve the clients increases linearly with the number of clients and thus does not scale well to large numbers of clients. The bandwidth can be reduced by “batching” clients, that is, by delaying the transmission of the program to a first client request for some interval in the hope that additional client requests for the same item will be received, and then serving all clients in a batch with a single stream. However, the bandwidth savings achieved by batching is, under standard assumptions about client request times, inversely proportional to the delay imposed in the start of the data transmission for at least some clients.